/**
 * @file bicon.c
 * @brief Finds biconnected components of a graph using the algorithm in 
 * Baase, "Computer Algorithms", 2nd edition, pg. 190.
 * @author Matthias Stallmann @date 1991
 * $Id: bicon.c 10 2007-06-28 20:08:57Z mfms $
 *
 * Because of GDR's convention that vw and wv are the same edge,
 *	regardless of which endpoint it's being viewed from, the
 *	manipulation of the edge stack had to modified.
 *
 *    The problem with the Baase algorithm is that both vw and wv
 *    end up on the stack (for a tree edge vw) and sometimes wv
 *    appears on top of other edges out of w.  These latter edges
 *    are not popped when they should be.
 *
 *    This implementation gets around the problem by pushing a
 *    back edge only if it doesn't go back to the parent.
 */

/*
 *  Copyright (C) 1991  Matthias Stallmann.
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

/* animation specific definitions */
#include<stdio.h>
#include "Gdr.h"
#define COUNT 3                 /* number of blinks */
#define XW 1                    /* prompt window coordinates */
#define YW 1
#define LBL_SIZE 10             /* max number of chars in vertex or edge label */
#define MSG_SIZE 100            /* max number of chars in prompt window */
#define wait suspend_animation()
TWIN pwin;                      /* window for user prompts */
char msg[MSG_SIZE];
char vtx_label[LBL_SIZE];
char edg_label[LBL_SIZE];

int mark[MAX_VERTEX];
int dfs_num[MAX_VERTEX];        /* preorder number of this vertex */
int back[MAX_VERTEX];           /* back number of this vertex */
int pre;                        /* current preorder number */
int component;                  /* current component number */

typedef struct cell {
  struct cell *next;
  edge edg;
} *E_LIST;
E_LIST edge_stack = NULL;

void push_edge_stack(edge e)
{
  E_LIST new;
  
  new = (E_LIST)calloc(1,sizeof(struct cell));
  new->next = edge_stack;
  new->edg = e;
  edge_stack = new;
}

edge pop_edge_stack(void)
{
  E_LIST out = edge_stack;
  edge e;
  
  e = out->edg;
  edge_stack = edge_stack->next;
  free(out);
  return(e);
}

void visit(vertex v, vertex parent)
{
  edge e,f;
  vertex w;
  
  mark[v] = 1;
  dfs_num[v] = ++pre;
  back[v] = pre;
  
  sprintf(msg,"Start visit, vertex %d\nClick Resume to continue",v);
  write_text_window(pwin,msg);
  wait;
  hide_window(pwin);
  
  blink_vertex(v,COUNT);
  sprintf(vtx_label,"%d,%d",dfs_num[v],back[v]);
  change_vertex_label(v,vtx_label);
  expose_vertex_label(v);
  highlight_vertex(v);
  
  e = first_out_edge(v);
  while (e != NULL_EDGE) {
    blink_edge(e,COUNT);
    w = other_vertex(v,e);
    if (!mark[w]) {
      push_edge_stack(e);
      highlight_edge(e);
      visit(w,v);
      if (back[w] >= dfs_num[v]) {
        component++;
        do {	f = pop_edge_stack();
        sprintf(edg_label,"<%d>",component);
        change_edge_label(f,edg_label);
        expose_edge_label(f);
        } while (!are_edges_equal(e,f));
      }
      else if (back[w] < back[v]) {
        back[v] = back[w];
        sprintf(vtx_label,"%d,%d",dfs_num[v],back[v]);
        change_vertex_label(v,vtx_label);
      }
    } else { /* w already in tree */
      if (w != parent && dfs_num[w] < dfs_num[v]) {
        push_edge_stack(e);
      }
      if (dfs_num[w] < back[v]) {
        back[v] = dfs_num[w];
        sprintf(vtx_label,"%d,%d",dfs_num[v],back[v]);
        change_vertex_label(v,vtx_label);
      }
    }
    
    e = next_out_edge(v,e);
  }
  sprintf(msg,"End visit, vertex %d\nClick Resume to continue",v);
  write_text_window(pwin,msg);
  wait;
  hide_window(pwin);
  
  un_highlight_vertex(v);
}

void bicon(void)
{
  vertex v;
  edge e;
  
  pre = 0; component = 0;
  for (v = 0; v < MAX_VERTEX; v++) mark[v] = 0;
  
  /* tell user what's going on */
  pwin = create_text_window(XW, YW,
                            "DFS starting at vertex 0\nClick Resume? to begin");
  wait;
  
  visit(0,NULL_VERTEX);
  
  write_text_window(pwin,"Ready for cleanup? (hit Resume if so)");
  wait;
  hide_window(pwin);
  
  /* cleanup: unhighlight the edges, erase all labels */
  for (e = first_edge(); e != NULL_EDGE; e = next_edge(e)) {
    change_edge_label(e,"");
    un_highlight_edge(e);
  }
  for (v = 0; v <= max_vertex(); v++)
    if (is_valid_vertex(v)) {
      change_vertex_label(v,"");
      hide_vertex_label(v);
    }
  
}

void animat(void) { bicon(); }

/*  [Last modified: 2007 06 28 at 19:41:57 GMT] */
